/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package org.osdtsystem.hierarchy;

import java.util.ArrayList;
import org.osdtsystem.options.CoverOptionsEngine;
import org.osdtsystem.options.CoverOptions;
import org.osdtsystem.dataset.HierarchyView;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import org.osdtsystem.utils.Storage;
import org.osdtsystem.dataset.Dataset;

/**
 * Abstract hierarchy class with common methods for hierarchies.
 * @param <H> the type of the classes in the hierarchy
 * @author Matthias Buch-Kromann
 */
public abstract class AbstractHierarchy<H extends HClass> implements Hierarchy<H> {
    final Class<H> type;
    final Storage storageAbstractFactory;
    final H topClass;
    final H emptyClass;
    private CoverOptions classificationParameters;
    
    public AbstractHierarchy(Class<H> type, Storage storage) {
        // Save type and storage
        this.type = type;
        this.storageAbstractFactory = storage;

        // Store top and empty class
        this.topClass = makeTopClass();
        this.emptyClass = makeEmptyClass();

        // Classification parameters
        classificationParameters = new CoverOptionsEngine();
    }

    /**
     * The intersection between two classes.
     * @param class1 the first class
     * @param class2 the second class
     * @return their intersection class
     */
    abstract H intersectionBinary(H class1, H class2);

    // Create top class
    abstract H makeTopClass();

    // Create empty class
    abstract H makeEmptyClass();

    @Override
    public final H topClass() {
        return topClass;
    }

    @Override
    public final H emptyClass() {
        return emptyClass;
    }

    @Override
    public final boolean isEmpty(H hclass) {
        return hclass == emptyClass;
    }

    @Override
    public final boolean isTop(H hclass) {
        return hclass == topClass;
    }

    @Override
    public final Class<H> hclassType() {
        return type;
    }

    @Override
    public final H intersection(H... hclasses) {
        // Sort arguments and check validity
        if (hclasses.length == 0)
            return topClass();
        
        // Compute intersection of all classes
        H intersection = hclasses[hclasses.length - 1];
        for (int i = hclasses.length - 2; i >= 0 && ! isEmpty(intersection); --i) {
            intersection = intersectionBinary(intersection, hclasses[i]);
        }

        // Return intersection
        return intersection;
    }

    @Override
    public H[] union(H... hclasses) {
        // Sort classes by increasing depth
        H[] sorted = Arrays.copyOf(hclasses, hclasses.length);
        Arrays.sort(sorted, depthComparator);

        // Check whether the classes in the union are subclasses of the preceding
        // classes
        int lastHigher = -1;
        int last = -1;
        int lastDepth = -1;
        int skip = 0;
        for (int i = 0; i < sorted.length; ++i) {
            // Find current hclass and stop if empty
            H hclass = sorted[i];
            if (isEmpty(hclass))
                break;

            // Previous classes are stored in indices 0 ... (i-1-skip): check
            // whether one of them contains the new class as a subclass
            boolean ignore = false;
            for (int j = 0; j <= lastHigher; ++j) {
                if (contains(sorted[j], hclass)) {
                    ignore = true;
                    break;
                }
            }

            // Ignore class or add it to list of classes and update depths
            if (ignore) {
                // The class is contained in one of the higher classes: skip it
                ++skip;
            } else {
                // Shift class to correct location if necessary
                if (skip > 0) {
                    sorted[i-skip] = hclass;
                }

                // Update lastHigher if depth was increased
                int newDepth = hclass.depth();
                if (lastDepth < newDepth) {
                    lastHigher = last;
                    lastDepth = newDepth;
                }

                // Update last
                last = i-skip;
                lastDepth = newDepth;
            }
        }

        // Return the surviving classes
        return Arrays.copyOf(sorted, last + 1);
    }

    @Override
    public boolean contains(H c1, H c2) {
        return intersectionBinary(c1, c2).equals(c2);
    }

    @Override
    public boolean contains(H hclass, HierarchyView<H> view, Dataset dataset, int identifier) {
        // This method can be overridden with a more efficient implementation
        return contains(hclass, dataClass(view, dataset, identifier));
    }

    @Override
    public HClass dataComponentClass(HierarchyView<H> view, Dataset dataset, int identifier, int dimension) {
        return componentClass(dataClass(view, dataset, identifier), dimension);
    }

    @Override
    public HClass dataComponentClassAtDepth(HierarchyView<H> view, Dataset dataset, int identifier, int dimension, int depth) {
        return componentClassAtDepth(dataClass(view, dataset, identifier), dimension, depth);
    }

    @Override
    public Collection<H> superclassesBelowRoot(HierarchyView<H> view,
            Dataset dataset, int identifier, H root, int minDepthBelowRoot, int maxDepthBelowRoot) {
        return superclassesBelowRoot(dataClass(view, dataset, identifier), root, minDepthBelowRoot, maxDepthBelowRoot);
    }

    @Override
    public List<H> superclassesBelowRoot(H hclass, H root, int minDepthBelowRoot, int maxDepthBelowRoot) {
        int rootDepth = root.depth();
        List<H> list = new ArrayList<H>();

        // Find all superclasses below root within the required depth limit
        for (H superClass : superclasses(hclass)) {
            int superClassDepth = superClass.depth() - rootDepth;
            if (superClassDepth >= minDepthBelowRoot && superClassDepth <= maxDepthBelowRoot
                    && contains(root, superClass))  {
                list.add(superClass);
            }
        }

        // Return list
        return Collections.unmodifiableList(list);
    }

    @Override
    public CoverOptions classificationParameters() {
        return classificationParameters;
    }

    @Override
    public HierarchyIterator<H> hierarchyIterator(H root, HierarchyView<H> view, Dataset dataset, int identifier) {
        return hierarchyIterator(root, dataClass(view, dataset, identifier));
    }

    @Override
    public Comparator<HClass> depthComparator() {
        return depthComparator;
    }

//    @Override
//    public Comparator<HClass> comparator() {
//        return depthComparator();
//    }

    private final Comparator<HClass> depthComparator =
            new Comparator<HClass>() {
            @Override
            public int compare(HClass o1, HClass o2) {
                // Check for equality
                if (o1 == o2)
                    return 0;

                // Then compare by depth (in increasing order)
                int cmp = o1.depth() - o2.depth();
                if (cmp != 0)
                    return cmp;

                // Finally compare by hash value
                return o1.hashCode() - o2.hashCode();
            }
        };
}
